Discrete Superlog
[crypto]
Discrete Superlog
You've heard of discrete log...now get ready for the discrete superlog.
- URL:
nc crypto.2020.chall.actf.co 20603
Recon
Opening a session gives something like
We define a^^b to be such that a^^0 = 1 and a^^b = a^(a^^(b-1)), where x^y represents x to the power of y.
Given this, find a positive integer x such that a^^x = b mod p.
Generating challenge 1 of 10...
p = 1169174076520537727987
a = 349507167920263434300
b = 349507167920263434300
Enter x:
Code
import pwn, random
got_flag = False
while not got_flag:
conn = pwn.remote('crypto.2020.chall.actf.co', 20603)
conn.recvuntil(b'a^^x = b mod p.\n')
for i in range(1, 11):
res = conn.recv()
if b'Wrong!' in res:
print(f'Challenge {i-1} failed..')
break
sp = res.decode().split('\n')
if len(sp) <= 4:
res = conn.recv()
sp = res.decode().split('\n')
p = int(sp[-4].split(' ')[2])
a = int(sp[-3].split(' ')[2])
b = int(sp[-2].split(' ')[2])
if (a == b):
choice = 1
else:
choice = pow(b, a, p)
print(f'Challenge {i}: Sending {choice}')
conn.send((str(choice) + '\n').encode())
if i == 10:
res = conn.recv()
print(res)
if not b'Wrong!' in res:
got_flag = True
conn.close()